package linkedlist;
import java.util.*;


class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class PracTice {
    //                    编写代码，以给定值x为基准将链表分割成两部分，所有⼩于x的结点排在⼤于或等于x的结点之前
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        //先判断特殊情况
        if (pHead == null){
            return null;
        }
        if (pHead.next == null){
            return pHead;
        }
        //一般情况
        //1.创建两个链表 分别保存 小于x值的 和大于等于x值的
        //傀儡节点
        ListNode smallHead = new ListNode(0);
        ListNode smallTail = smallHead;
        ListNode largeHead = new ListNode(0);
        ListNode largeTail = largeHead;
        //2.遍历链表然后尾插
        for (ListNode cur = pHead; cur != null; cur = cur.next){
            if (cur.val < x){
                smallTail.next = cur;
                smallTail = cur;
            } else {
                largeTail.next = cur;
                largeTail = cur;
            }
        }
        //2.拼接两个链表
        smallTail.next = largeHead.next;
        //3.需要把拼接后的链表的最后一个节点的 next 指向 null
        largeTail.next = null;
        //4.返回新链表的头节点
        return smallHead.next;
    }

    //                                            判断链表是否回文
    //方法一     空间复杂度为 O (1)
    public boolean chkPalindrome(ListNode A) {
        // write code here
        //特殊情况
        if (A == null) {
            return true;
        }
        if (A.next == null) {
            return true;
        }
        //一般情况
        //1.先找到链表的中间节点
        int size = size(A);
        ListNode B = A;
        for (int i = 0; i < (size / 2); i++) {
            B = B.next;
        }
        //2.将中间节点后面的链表逆序
        ListNode prve = null;
        ListNode cur = B;
        ListNode next = null;
        while (cur != null) {
            next = cur.next;
            if (next == null) {
                B = cur;
            }
            cur.next = prve;
            prve = cur;
            cur = next;
        }
        //3.判断是否回文
        ListNode cur1 = A;
        ListNode cur2 = B;
        while (cur1 != null && cur2 != null) {
            if (cur1.val == cur2.val) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            } else {
                return false;
            }
        }
        return true;
    }
    public int size(ListNode head) {
        int size = 0;
        for (ListNode cur = head; cur != null; cur = cur.next) {
            size++;
        }
        return size;
    }
    //方法二    空间复杂度为 O(n)
    public boolean chkPalindrome2(ListNode A) {
        // write code here
        //特殊情况
        if (A == null){
            return true;
        }
        if (A.next == null){
            return true;
        }
        //一般情况
        //1.赋值一份新的链表 头节点用newHead指向
        ListNode newHead = new ListNode(0);
        ListNode newTali = newHead;
        //遍历 A 链表
        for (ListNode cur = A; cur != null; cur = cur.next){
            ListNode newNode = new ListNode(cur.val);
            newTali.next = newNode;
            newTali = newNode;
        }
        //傀儡节点不再使用
        newHead = newHead.next;
        //2.新链表逆序
        ListNode prve = null;
        ListNode cur = newHead;
        ListNode next = null;
        while(cur != null){
            next = cur.next;
            cur.next = prve;
            if (next == null){
                newHead = cur;
            }
            prve = cur;
            cur = next;
        }
        //3.判断是否回文
        ListNode cur1 = A;
        ListNode cur2 = newHead;
        while (cur1 != null && cur2 != null){
            if(cur1.val == cur2.val){
                cur1 = cur1.next;
                cur2 = cur2.next;
            } else {
                return false;
            }
        }
        return true;
    }
    //                                        判定链表相交
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //1.先找到长的链表
        int sizeA = size(headA);
        int sizeB = size(headB);
        //2.让长的链表先走 长度插值步
        ListNode curA = headA;
        ListNode curB = headB;
        if (sizeA < sizeB){
            for (int i = 0; i < sizeB - sizeA; i++){
                curB = curB.next;
            }
        } else {
            for (int i = 0; i < sizeA - sizeB; i++){
                curA = curA.next;
            }
        }
        //3.两个链表一起往后走，判断是否相交
        while (curA != null && curB != null){
            if (curA == curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
//    public int size(ListNode head){
//        int size = 0;
//        for (ListNode cur = head; cur != null; cur = cur.next){
//            size++;
//        }
//        return size;
//    }

    //                                                     判断链表带环
    //方法一   时间复杂的为 O(n) 空间复杂度为 O(1)
    public boolean hasCycle(ListNode head) {
        //特殊情况
        if (head == null){
            return false;
        }
        //双指针法
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                return true;
            }
        }
        return false;
    }
    //方法二    时间复杂的为 O(n2) 空间复杂度为 O(n)
    public boolean hasCycle2(ListNode head) {
        //特殊情况
        if (head == null){
            return false;
        }
        //创建一个顺序表存放 链表元素的地址
        ArrayList<ListNode> list = new ArrayList<>();
        //
        for (ListNode cur = head; cur != null; cur = cur.next){
            if (list.contains(cur)){
                return true;
            } else {
                list.add(cur);
            }
        }
        return false;
    }

    //                                        求环的入口点
    public ListNode detectCycle(ListNode head) {
        //特殊情况
        if (head == null){
            return null;
        }
        if (head.next == null){
            return null;
        }
        //一、判断是否有环
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                break;//说明有环
            }
        }
        //两种情况, 1有环 2.无环
        if (fast == null || fast.next == null){
            return null;
        }
        //走到这说明有环
        //二、创建 cur1 指向头节点, cur2 指向 fast 和 slow 重合的位置
        ListNode cur1 = head;
        ListNode cur2 = fast;
        while (cur1 != cur2){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }
}
